大鱼吃小鱼 [思维题]
大鱼吃小鱼 [思维题]
51nod 1289
近一个月的颓废后的第一篇博客。最近一直在刷51nod，感觉题目质量还比较好，所以在按照难度从下往上刷。这题是个比较水的思维题。
题目来源: 51nod
分析
读完题后，我们首先需要注意到的是"足够长的时间"。这其实意味着最后的存活的鱼一定满足一个状态：所有的鱼可以分为两部分，左半部分向左游，右半部分向右游。
那么，我们可以从这点入手。我们以向左游的鱼为例。显然的，对于第i条鱼，它要存活，必须要比它能遇到的所有向右游的鱼大。而哪些鱼是它能遇到的呢？是介于上一条向左游的存活的鱼j和这条鱼中间的鱼。因为j之前的向右的鱼一定都被j或其它鱼吃掉了，否则j不会存活。
所以我们只需要动态的维护一个最大值maxn。对于向左游的鱼，我们从左向右遍历，若当前的鱼比maxn大且向右游，则更新maxn；若当前的鱼比maxn大且向左游，则令maxn=0，且这条鱼可以存活。然后对于向右的鱼同理，只不过数组要从右向左遍历。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| #include <iostream>
#include <algorithm>
#define MAXN 100100
using namespace std;
int a[MAXN], b[MAXN];
int main()
{
int n;
cin >> n;
for (int i = 1; i<=n; i++)
cin >> a[i] >> b[i];
int ans = 0;
int maxn = 0;
for (int i = 1; i<=n; i++)
if (a[i]>maxn)
{
if (b[i]==0)
{
ans ++;
maxn = 0;
}else
maxn = a[i];
}
maxn = 0;
for (int i = n; i>=1; i--)
if (a[i]>maxn)
{
if (b[i]==1)
{
ans ++;
maxn = 0;
}else maxn = a[i];
}
cout << ans << endl;
return 0;
}
|